package main

import "fmt"

func levenshteinDistance(s, t string) int {
	if s == t {
		return 0
	}

	lenS := len(s)
	lenT := len(t)

	if lenS == 0 {
		return lenT
	}
	if lenT == 0 {
		return lenS
	}

	d := make([][]int, lenS+1)
	for i := range d {
		d[i] = make([]int, lenT+1)
		d[i][0] = i
	}
	for j := range d[0] {
		d[0][j] = j
	}

	for j := 1; j <= lenT; j++ {
		for i := 1; i <= lenS; i++ {
			cost := 1
			if s[i-1] == t[j-1] {
				cost = 0
			}
			d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+cost)
		}
	}

	return d[lenS][lenT]
}

// min 返回三个整数中的最小值
func min(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
		return c
	}
	if b < c {
		return b
	}
	return c
}

// similarity 计算两个字符串的相似度
func similarity(s, t string) float64 {
	maxLen := len(s)
	if len(t) > maxLen {
		maxLen = len(t)
	}
	return 1.0 - (float64(levenshteinDistance(s, t)) / float64(maxLen))
}

func main() {
	s := "kitten"
	t := "sdfdgkdfging"

	fmt.Printf("The Levenshtein distance between %q and %q is %d.\n", s, t, levenshteinDistance(s, t))
	fmt.Printf("The similarity between %q and %q is %.2f.\n", s, t, similarity(s, t))
}
